package com.zhang.sort;

import com.zhang.Student;
import com.zhang.sort.cmp.ShellSort;

import java.text.DecimalFormat;
import java.util.Comparator;

/**
 * @author 张吉鑫
 * @Description 排序抽象类
 * @date 2021/4/11 16:52
 */
public abstract class Sort<E> implements Comparable<Sort<E>>{
    /**
     * 需要排序的数组
     */
    protected E[] array;
    /**
     * 比较次数
     */
    private int cmpCount;
    /**
     * 交换次数
     */
    private int swapCount;
    /**
     * 排序时间
     */
    private long time;
    /**
     * 比较器
     */
    private Comparator comparator;
    /**
     * 保留小数点后两位
     */
    private DecimalFormat fmt = new DecimalFormat("#.00");


    public void sort(E[] array){
        sort(array, null);
    }

    /**
     * 如果元素为空或者元素数量少于2 直接返回不需要排序
     * 获取当前时间 记录排序算法需要的时间
     * @param array
     * @param comparator
     */
    public void sort(E[] array,Comparator comparator) {
        if (array == null || array.length < 2) {
            return;
        }
        this.comparator = comparator;

        this.array = array;

        long begin = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - begin;
    }

    /**
     * 排序抽象方法 由子类实现方法
     */
    protected abstract void sort();

    /**
     * 传入元素索引 比较元素大小
     * @param i1 元素的索引
     * @param i2 元素的索引
     * @return 返回比较结果
     */
    protected int cmp(int i1, int i2) {
        return cmpElement(array[i1],array[i2] );
    }

    /**
     * 比较器 比较数组元素的大小 并记录比较次数
     * @param v1 元素一
     * @param v2 元素二
     * @return 返回比较结果
     */
    protected int cmpElement(E v1, E v2) {
        cmpCount++;
        if (comparator != null){
            return comparator.compare(v1, v2);
        }
        return ((Comparable)v1).compareTo(v2);
    }

    /**
     * 交换索引元素的位置 并记录交换次数
     * @param i1 元素一的索引
     * @param i2 元素二的索引
     */
    protected void swap(int i1, int i2) {
        swapCount++;
        E tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    /**
     * 重写比较器 时间少的排在前面 如果时间相当 就比较交换次数
     * @param o 排序算法实现类
     * @return 返回比较结果
     */
    @Override
    public int compareTo(Sort<E> o) {
        int result = (int)(time - o.time);
        if (result != 0) {
            return result;
        }

        result = cmpCount - o.cmpCount;
        if (result != 0) {
            return result;
        }

        return swapCount - o.swapCount;
    }

    /**
     * @return 打印算法的时间复杂度 比较次数 交换次数 调用方法测试当前算法是否稳定
     */
    @Override
    public String toString() {
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
        String stability = "稳定：" + stability();
        return "【" + getClass().getSimpleName() + "】\n"
                + stability + " \t"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";

    }

    /**
     * 美化打印次数显示
     * @param number 需要美化的数据
     * @return 返回美化结果
     */
    private String numberString(int number) {
        if (number < 10_000) {
            return "" + number;
        }

        if (number < 10_000_0000) {
            return fmt.format(number / 10000.0) + "万";
        }
        return fmt.format(number / 100000000.0) + "亿";
    }

    /**
     * 判断当前算法是否稳定
     * @return 稳定返回true 不稳定返回false
     */
    private boolean stability(){
        if (this instanceof ShellSort){
            return false;
        }
        if (this instanceof CountingSort){
            return false;
        }
        if (this instanceof CountingSort2){
            return true;
        }
        if (this instanceof RadixSort){
            return true;
        }
        if (this instanceof BucketSort){
            return true;
        }
        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((E[]) students);
        for (int i = 0; i < students.length - 1; i++) {
            if ((students[i].score + 10) != students[i + 1].score){
                return false;
            }
        }
        return true;
    }

}
